package week2.Chapter3.Chapter4;

import java.util.*;

/**
 * MazeSolver attempts to recursively traverse a Maze. The goal is to get
 * from the given starting position to the bottom right, following a path
 * og l's. Arbitraryconstants are used to represent locations in the maze
 * that have been TRIED and that are part of the solution PATH
 *
 *@author Lewis and Chase
 *@version 4.0
 */
public class MazeSolver {
    private Maze maze;

    /**
     * Constructor for the MazeSolver class
     * @param maze
     */
    public MazeSolver(Maze maze) {
        this.maze = maze;
    }

    /**
     * Attemptsto recursively traverse the maze. Inserts special
     * characters indicating locations that have been TRIED and that
     * evevntually become part of the solution PATH
     *
     * @paramrow row the index of the row to current location
     * @paramcolumn column  the index of the column to current location
     * @return ture if the maze has been solved
     */
    public boolean traverse() {
        boolean done = false;
        int row, column;
        Position pos = new Position();
        Deque<Position> stack = new LinkedList<Position>();
        stack.push(pos);

        while(!(done)&&!stack.isEmpty())
        {
            pos = stack.pop();
            //this cell has been tried
            maze.tryPosition(pos.getx(), pos.gety());
            if (pos.getx() == maze.getRows() - 1 && pos.gety() == maze.getColumns() - 1) {
                done = true;//the maze is solved
            } else {
                push_new_pos(pos.getx() - 1, pos.gety(), stack);
                push_new_pos(pos.getx() + 1, pos.gety(), stack);
                push_new_pos(pos.getx(), pos.gety() - 1, stack);
                push_new_pos(pos.getx(), pos.gety() + 1, stack);
            }
        }
        return done;
    }

    /**
     * Push a new attempted move onto the stack
     *
     * @param x represents x coordinate
     * @param y represents y coordinate
     * @param stack the working stack of moves within the grid
     * @return stack of move within the grid
     */
    private void push_new_pos ( int x, int y, Deque<Position> stack){
        Position npos = new Position();
        npos.setx(x);
        npos.sety(y);
        if(maze.validPosition(x,y)) {
            stack.push(npos);
        }
    }
}
